#leetcode题目39：组合总和
#难度：中等
#时间复杂度：O(n^2)
#空间复杂度：O(1)
#方法：回溯

from typing import List
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        

        if not candidates:
            return []

        def dfs(res,path,target,index):
            if target==0:#停止条件
                res.append(path[:])

            for i in range(index,len(candidates)):
                if target>=candidates[i]:
                    path.append(candidates[i])
                    dfs(res,path,target-candidates[i],i)
                    path.pop()

        res=[]
        dfs(res,[],target,0)
        return res


#测试数据
candidates=[2,3,6,7]
target=7
#预期输出：[[2,2,3],[7]]
solution=Solution()
print(solution.combinationSum(candidates,target))

candidates=[2,3,5]
target=8
#预期输出：[[2,2,2,2],[2,3,3],[3,5]]
solution=Solution()
print(solution.combinationSum(candidates,target))

candidates=[2]
target=1
#预期输出：[]
solution=Solution()
print(solution.combinationSum(candidates,target))
